Present day ultra-large-scale integration (ULSI) circuits may include hundreds of thousands or millions of interconnected active electronic devices on an integrated circuit chip. The large capital investment required to fabricate and test large scale integrated circuits prior to sale to a customer and the difficulty, expense and loss of goodwill associated with reworking and replacing integrated circuits which fail to operate as planned, have increased the need to accurately characterize the electrical behavior of integrated circuits prior to their manufacture.
Moreover, now that submicron and deep-submicron (0.5 μm and below) technologies have begun to dominate silicon chip manufacturing and the prospect of million-plus-gate chips operating at clock rates of 100 MHZ has become a reality, fundamental changes have had to be made to conventional integrated circuit design methodologies and the electronic design automation (EDA) tools based thereon. To meet the challenges posed by such large-scale circuits, techniques have been developed to represent integrated circuit designs at various levels of abstraction. According to these techniques, an integrated circuit design may be represented by an electrical schematic containing devices and nets interconnecting the devices and by geometric layout data that describes patterns of regions or elements to be formed in and/or on an integrated circuit substrate (e.g., wafer).
Techniques for managing highly integrated circuit designs include hierarchical design techniques. Using such techniques, a particular design is partitioned into functional cells and cells-within-cells, etc., so that at a given level of hierarchy the design may be analyzed as a set of cells and their respective interconnections, without being concerned with all the details of the contents of the cells (e.g., subcells within each cell).
These hierarchical techniques can be essential to the efficient performance of computer-assisted integrated circuit design verification. Such verification may include operations to perform layout versus schematic comparison (LVS) using computer-based design tools. As will be understood by those skilled in the art, tools to perform layout versus schematic comparison may include extraction software to extract a layout netlist from geometric layout data. An extracted layout netlist is then compared to an electrical schematic netlist to determine functional equivalence between the original integrated circuit schematic and the integrated circuit layout. One difficulty associated with the performance of these operations may be caused by a dissimilarity in the labeling of nets and devices in the extracted layout netlist relative to the electrical schematic netlist.
Conventional methods for determining correspondence between an electrical schematic netlist and a layout netlist are described in U.S. Pat. No. 5,249,133 to Batra entitled “Method for the Hierarchical Comparison of Schematics and Layouts of Electronic Components”; U.S. Pat. No. 5,463,561 to Razdan entitled “High Capacity Netlist Comparison”; and U.S. Pat. No. 5,243,538 to Okuzawa et al. entitled “Comparison and Verification System for Logic Circuits and Method Thereof.” Another conventional method for determining correspondence includes operations to represent the electrical schematic netlist and the layout netlist as a schematic graph and a layout graph, respectively. Each of these graphs may be represented as bipartite graphs having vertices (also referred to herein as “nodes”) that represent devices and nets within their respective netlists. LVS software is then used to determine an isomorphism between the bipartite graphs.
The unambiguous determination of isomorphism between two arbitrary graphs may be a computationally intractable problem. To address this problem, heuristic methods for identifying graph isomorphisms with acceptable reliability and efficiency for ULSI designs have been developed. One generally established heuristic method is an iterative graph-coloring method described in articles by C. Ebeling and O. Zajicek entitled “Validating VLSI Circuit Layout By Wirelist Comparison,” Proceedings of ICCAD, pp. 172–173 (1983); and by C. Ebeling entitled “Gemini II: A Second Generation Layout Validation Program,” IEEE ICCAD-88, Digest of Technical Papers, pp. 322–325, Nov. 7–10 (1988), the disclosures of which are hereby incorporated herein by reference. As described in these articles, an integer node value (color) is assigned to each node of a bipartite graph of the electrical schematic netlist and the extracted layout netlist, based on a graph invariant such as “number of nearest neighbors” (i.e., number of adjacent nodes/vertices). Each node is iteratively recolored as a function of the colors of its neighbors, until the maximum number of unique colors is achieved (i.e., an equilibrium state is achieved). Because these operations are independent of labeling, equivalent schematic and layout netlists generally will be represented by the same set of colors. A one-to-one correspondence may then be achieved by simply matching up each node in the schematic graph with a node in the layout graph that has the same color.
Unfortunately, some circuits may exhibit symmetry that may cause different nodes to receive the same color because the “neighborhoods” associated with these nodes are similar. When two or more nodes have the same color, ambiguities in selecting matching nodes may arise. Typically, this situation is handled by making a guess as to which ones of the nodes in the schematic graph correspond to the same colored nodes in the layout graph, then assigning new colors to the matched nodes and then recoloring. If the guess was incorrect, a number of nodes may fail to match when the matching is applied at the next level of hierarchy, even though an alternate guess might have resulted in a complete one-to-one mapping.
For example, the AND-OR-INVERT (AOI) cell of FIG. 1 exhibits a number of symmetries with respect to input A because input A may be independently swapped with input B or input A may be swapped with input C if and only if input B is also swapped with input D. Similar symmetries also exist with respect to inputs B, C and D. FIG. 2 illustrates an original electrical schematic (S1) of the AOI cell and an extracted layout schematic (L1) of the AOI cell. FIG. 3 illustrates an original electrical schematic (S2) which contains the AOI cell S1 of FIG. 2 as a child cell and an extracted layout schematic (L2) which contains the AOI cell L1 of FIG. 2 as a child cell. As will be understood by those skilled in the art, verification of the schematics of FIG. 3 will only be concerned with the mapping of ports (W,X,Y,Z) of the AOI cell L1 of FIG. 2 to the ports (Q,R,S,T) of the schematic S2 of FIG. 2. However, because the symmetry of the design may cause the ports of each AOI child cell in FIG. 2 to acquire the same color when the schematic and layout graphs of the AOI child cells have been colored to an equilibrium state, a conventional LVS tool may make an arbitrary mapping which may be incorrect (e.g., Q→W, R→Y, S→X, T→Z). A consequence of this arbitrary mapping may be manifested at the next level of hierarchy.
For example, as illustrated by FIG. 3, an incorrect choice in the mapping of S1 to L1 (i.e., the child cells) may cause S2 and L2 (i.e., the parent cells) to be reported as nonequivalent after a coloring algorithm has been performed on the schematic and layout graphs at the parent level. Here, devices D1–D4 are distinct devices that are connected between the ports of the AOI “child” cell and the ports of the “parent” cell. Thus, LVS software may report a mismatch between an original electrical schematic netlist and an extracted layout netlist, even though it is possible to make assignments among symmetric nodes that will result in a match. Typically, a consequence of this limitation in LVS software is that the software user must manually intervene by providing the LVS software with specific assignments to resolve ambiguities due to symmetry. Since it is not always clear where an erroneous guess was made, such manual intervention may be time consuming. For large and highly symmetric designs such as memories and gate arrays, these limitations may significantly reduce the utility of conventional LVS tools including hierarchical LVS tools using general-purpose graph isomorphism algorithms. In particular, the high degree of symmetry associated with large memories may force numerous arbitrary matchings or guesses to be made between layout and schematic. These guesses may preclude matching in the parent cells of the memories if the parent cells use permutations of the memory ports that are valid by virtue of the symmetries, but are inconsistent with the guesses.
To address some of these limitations associated with conventional verification tools, an LVS software tool 100 has been developed to determine equivalency between an integrated circuit schematic and an integrated circuit layout, using the operations 102–114 illustrated by the flow diagram of FIG. 4. This LVS software tool may be embodied in a commercially available product from the assignee of the present application, Avant! Corporation of Fremont, Calif. This software product, which is marketed under the tradename Hercules™, is more fully described in an instruction manual by the same name, Release 2.1, January (1997), the disclosure of which is hereby incorporated herein by reference. In particular, the LVS software tool of FIG. 4 can perform the operations of generating a hierarchical electrical schematic netlist having at least one parent cell and a plurality of child cells in the parent cell, Block 102, and extracting a corresponding integrated circuit layout as a hierarchical layout netlist, Block 104. An operation is also performed to generate at least one color symmetrizing matrix corresponding to a child cell in the schematic netlist, Block 106. Here, the child cell may have a number of symmetries which, when taken alone or in combination, may result in a number of electrically equivalent permutations of the child cell. As illustrated by Block 108, operations are then performed to generate schematic and layout graphs of the parent cells in the schematic and layout netlists, respectively. These graphs are similar to the above-described bipartite graphs. The nodes in the schematic graph are then colored and a first color symmetry vector is generated for a child cell in the schematic graph. Similarly, the nodes in the layout graph are colored and a second color symmetry vector is generated for a child cell in the layout graph, Block 110.
An operation is then performed to determine an equivalency between the colors of the nodes in the schematic and layout graphs based on a selected permutation of the child cell in the layout graph, Block 112, and then an operation is performed to determine a vector equivalency between a product of the color symmetrizing matrix and the first color vector and a product of the color symmetrizing matrix and the second color vector, Block 114. Finally, a membership test is automatically performed at Block 116 to determine whether the selected permutation of the child cell can be derived from the valid symmetries associated with that child cell. As described in a textbook authored by G. Butler, entitled Fundamental Algorithms for Permutation Groups, Springer-Verlag, p. 144 (1991), a Furst-Hopcroft-Luks version of a Schreier-Sims method may be performed. Unfortunately, although the software tool of FIG. 4 typically requires no human intervention and works well with most designs exhibiting symmetry, the automatic performance of membership test to validate the accuracy of the matched layout and schematic may incur an unduly large computational expense and limit the applicability of the above software to large integrated circuit designs having large degrees of symmetry.
Thus, notwithstanding the above described attempts, there continues to be a need to provide verification tools which have the capability of automatically resolving ambiguities in symmetric circuits. Such tools should be conservative in the identification of graph isomorphism, in the sense that if any ambiguities remain after the verification operations are performed, a nonisomorphism result should be generated and the circuits should be designated as non-equivalent even if they may be equivalent. This is because the penalty for erroneously identifying equivalent circuits as nonequivalent (i.e., manual intervention by the user) is far less onerous than the penalty for misidentifying non-equivalent circuits as equivalent (i.e., the expense of prototyping and manufacturing an incorrect design).